#include "syntax.h"
#include <bitset>
#include <cstring>
#include <iostream>
#include <map>
#include <vector>
#include <queue>

using std::cin;
using std::cout;
using std::endl;
using std::ostream;
using tool::Graph;
using namespace cp;

std::vector<Symbol> cp::symbols;
std::vector<Production> cp::prods;
std::stack<Token*> cp::ts;
std::stack<int> cp::ss;

namespace{
const int TermCount = SymbolCount - NonTermCount;
const int TermStart = NonTermCount;
inline bool isTerm(int id) {return id >= NonTermCount;}
inline int termID(int id) {return id - NonTermCount;}
bool nullable[NonTermCount];
enum{Error = 0, Accept, Reduce, Shift};
const char* typeName[] = {
	"Error", "Accept", "Reduce", "Shift"
};
struct ActionInfo{
	int type, next, prodID;
	ActionInfo():type(Error),next(0),prodID(0){}
};

typedef std::map<int, ActionInfo> AEdge;
typedef std::map<int, int> GEdge;
std::vector<AEdge> actionTable;
std::vector<GEdge> gotoTable;

std::bitset<TermCount> first[NonTermCount], follow[NonTermCount];
std::bitset<ProdCount> derive[NonTermCount];

template <int N>
inline void writeBack(Graph &graph, std::bitset<N> bss[]){
	graph.foreach([&graph, bss](int b, int e){
		if (graph.connect(b, e)) bss[b] |= bss[e];
	});
}

void buildNullable(){
	bool temp[NonTermCount];
	memset(temp, 0, sizeof(temp));
	for (Production& prod : prods)
			nullable[prod.left] = prod.right.empty();
	bool *last = temp, *cur = nullable;
	auto check = [](bool* last, bool* cur){
		for (int i = 0; i < NonTermCount; ++i)
			if (cur[i] != last[i]) return false;
		return true;
	};
	auto update = [](Production &prod, bool* last, bool* cur){
		for (int &i : prod.right) if (!last[i]) return;
		cur[prod.left] = true;
	};

	while(!check(last, cur)){
		std::swap(last, cur);
		for (Production& prod : prods)
			update(prod,last,cur);
	}
	if (cur != nullable) memcpy(nullable, temp, sizeof(nullable));
}

void buildFirst(){
	Graph graph(NonTermCount);
	for (Production& prod : prods){
		for (int &i : prod.right){
			if (isTerm(i)) {first[prod.left].set(termID(i)); break;}
			graph.setEdge(prod.left, i);
			if (!nullable[prod.left]) break;
		}
	}
	graph.closure();
	writeBack<TermCount>(graph, first);
}

void buildFollow(){
	Graph graph(NonTermCount);
	follow[prods[0].left].set(termID(*prods[0].right.rbegin()));
	for (Production& prod : prods){
		auto& right = prod.right;
		if (right.empty()) continue;
		for (size_t i = 0, j = 1; j < right.size(); ++i, ++j){
			if (isTerm(right[i])) continue;
			if (isTerm(right[j])) follow[right[i]].set(termID(right[j]));
			else follow[right[i]] |= first[right[j]];
		}
		for (auto iter = right.rbegin(); iter != right.rend(); ++iter){
			if (isTerm(*iter)) break;
			graph.setEdge(*iter, prod.left);
			if (!nullable[*iter]) break;
		}
	}
	graph.closure();
	writeBack<TermCount>(graph, follow);
}

void buildDerive(){
	for (int i = 0; i < ProdCount; ++i)
		derive[prods[i].left].set(i);
	Graph graph(NonTermCount);
	for (Production& prod : prods){
		for (int &i : prod.right){
			if (isTerm(i)) break;
			graph.setEdge(prod.left, i);
			if (!nullable[i]) break;
		}
	}
	writeBack<ProdCount>(graph, derive);
}

struct Item{
	size_t prodID, pos;
	Item(int _prodID, int _pos = 0):prodID(_prodID),pos(_pos){}
	int curSymbolID()const{
		return pos >= prods[prodID].right.size() ? -1 : prods[prodID].right[pos];
	}
	void pushForward(){++pos;}
	friend bool operator < (const Item& lf, const Item& rt){
		return lf.pos != rt.pos ?
				lf.pos < rt.pos :
				prods[lf.prodID] < prods[rt.prodID];
	}
	friend ostream& operator << (ostream& os, const Item& item){
		os << item.pos << ' ' << prods[item.prodID];
		return os;
	}
};

struct ItemSet{
	std::set<Item> items;
	void insert(const Item &item){ items.insert(item); }
	void clear(){ items.clear(); }
	void closure(){
		std::bitset<ProdCount> set;
		for (const Item& item : items){
			int curID = item.curSymbolID();
			if (curID >= 0 && !isTerm(curID))
				set |= derive[curID];
		}
		for (int i = 0; i < ProdCount; ++i)
			if (set[i]) items.insert(Item(i, 0));
	}
	friend bool operator < (const ItemSet& lf, const ItemSet& rt){
		return lf.items < rt.items;
	}
	friend ostream& operator << (ostream& os, const ItemSet& is){
		for (const Item& item : is.items)
			os << item << endl;
		return os;
	}
};

struct ItemSetGraph{
	typedef std::map<int, ItemSet*> Edge;
	struct CMP{
		bool operator()(const ItemSet* lf, const ItemSet* rt) const{
			return *lf < *rt;
		}
	};
	typedef std::map<ItemSet*, Edge, CMP> Graph;
	Graph graph;
	void clear(){
		for (auto iter = graph.begin(); iter != graph.end(); ++iter)
			if (iter->first) delete iter->first;
		graph.clear();
	}
	~ItemSetGraph(){clear();}

	friend ostream& operator << (ostream& os, const ItemSetGraph& isg){
		// 对每个ItemSet编号
		std::map<ItemSet*, int> map;
		std::map<int, ItemSet*> map1;
		int ip = 0;
		for (auto iter = isg.graph.begin(); iter != isg.graph.end(); ++iter){
			map[iter->first] = ip;
			map1[ip++] = iter->first;
		}

		for (auto iter = map1.begin(); iter != map1.end(); ++iter)
			os << iter->first << " :\n" << *iter->second << endl;

		for (auto iter = isg.graph.begin(); iter != isg.graph.end(); ++iter){
			const Edge &edge = iter->second;
			for (auto iter1 = edge.begin(); iter1 != edge.end(); ++iter1)
				os << symbols[iter1->first] << " : " << map[iter->first] << " -> " << map[iter1->second] << endl;
		}
		return os;
	}

	void build(){
		clear();
		ItemSet* front = new ItemSet;
		front->insert(Item(0,0));
		front->closure();

		graph.insert(std::pair<ItemSet*,Edge>(front, Edge()));
		std::queue<ItemSet*> qu;
		qu.push(front);
		while (!qu.empty()){
			front = qu.front();
			qu.pop();
			Edge &edge = graph[front];
			for (const Item& item : front->items){
				int curID = item.curSymbolID();
				if (curID < 0) continue;
				if (edge.find(curID ) == edge.end())
					edge[curID] = new ItemSet;
				Item temp(item);
				temp.pushForward();
				edge[curID]->insert(temp);
			}
			for (auto iter = edge.begin(); iter != edge.end(); ++iter){
				ItemSet* is = iter->second;
//				cout << *is << endl;
				is->closure();
//				cout << *is << endl;
				auto tar = graph.find(is);
				if (tar == graph.end()){
					graph.insert(std::pair<ItemSet*,Edge>(is, Edge()));
					qu.push(is);
				}
				else {
					delete is;
					iter->second = tar->first;
				}
			}
		}
	}
};

void buildPDA(ItemSetGraph &isg){
	ItemSetGraph::Graph &graph = isg.graph;
	actionTable.assign(graph.size(), AEdge());
	gotoTable.assign(graph.size(), GEdge());

	int id = 0;
	std::map<ItemSet*, int> map;
	for (auto iter = graph.begin(); iter != graph.end(); ++iter)
		map[iter->first] = id++;

	auto setReduce = [](int cur, int prodID){
		int left = prods[prodID].left;
		for (int i = 0; i < TermCount; ++i){
			if (!follow[left][i]) continue;
			ActionInfo &info = actionTable[cur][i+TermStart];
			if (info.type == Reduce || info.type == Accept){
				cout << "状态" << cur << ":\n";
				cout << "规约/规约冲突，\n原产生式为 ";
				cout << prods[info.prodID] << ", 优先级为" << prods[info.prodID].pri << endl;
				cout << "现产生式为 " << prods[prodID] << ", 优先级为" << prods[prodID].pri << endl;
				if (prods[prodID].pri < prods[info.prodID].pri) return;
				info.prodID = prodID;
				info.type = prodID ? Reduce : Accept;
				continue;
			}
			else if (info.type == Shift){
				cout << "状态" << cur << ":\n";
				cout << "移进/规约冲突,\n原移进方向为通过 ";
				cout << symbols[i+TermStart] << " 到 " << info.next << ", 符号优先级为" << symbols[i+TermStart].pri << endl;
				cout << "现产生式为 " << prods[prodID] << ", 优先级为" << prods[prodID].pri << endl;
			}

			if (info.type != Error && prods[prodID].pri < symbols[i+TermStart].pri)
				continue;
			info.prodID = prodID;
			info.type = prodID ? Reduce : Accept;
		}
	};

	auto setShift = [](int cur, int dst, int symID){
		ActionInfo &info = actionTable[cur][symID];
		if (info.type == Shift) return;
		if (info.type != Error){
			cout << "状态" << cur << ":\n";
			cout << "移进/规约冲突,\n原产生式为" << prods[info.prodID] << ", 优先级为" << prods[info.prodID].pri << endl;
			cout << "现移进方向是通过 ";
			cout << symbols[symID] << " 到 " << info.next << ", 符号优先级为" << symbols[symID].pri << endl;
		}
		if (info.type != Error && prods[info.prodID].pri > symbols[symID].pri)
			return;
		info.type = Shift;
		info.next = dst;
	};

	auto setGoto = [](int cur, int dst, int symID){
		gotoTable[cur][symID] = dst;
	};

	for (auto iter = graph.begin(); iter != graph.end(); ++iter){
		ItemSet* is = iter->first;
		int cur = map[is];
		for (const Item& item : is->items){
			int curSymID = item.curSymbolID();
			if (curSymID < 0) {	setReduce(cur, item.prodID);continue;}
			int dst = map[iter->second[curSymID]];
			if (!isTerm(curSymID)) setGoto(cur, dst, curSymID);
			else setShift(cur, dst, curSymID);
		}
	}
}

void displayTransfer(std::ostream &os){
	os << "------------------------------" << endl;
	os << "action:" << endl;
	for (size_t i = 0; i < actionTable.size(); ++i){
		const AEdge& ae = actionTable[i];
		os << i << ":" << endl;
		for (auto iter = ae.begin(); iter != ae.end(); ++iter){
			if (iter->second.type == Shift)
				os << "shift, via " << symbols[iter->first] << " to " << iter->second.next << endl;
			else{
				os << (iter->second.type == Reduce ? "reduce" : "accept");
				os << ", before " << symbols[iter->first] << " to " << prods[iter->second.prodID] << endl;
			}
		}
		os << endl;
	}

	os << "goto" << endl;
	for (size_t i = 0; i < gotoTable.size(); ++i){
		os << i << ":" << endl;
		const GEdge &ge = gotoTable[i];
		for (auto iter = ge.begin(); iter != ge.end(); ++iter)
			os << "via " << symbols[iter->first] << " to " << iter->second << endl;
		os << endl;
	}

	os << "------------------------------" << endl;
}

}

void cp::initPDA(){
	// 打印各种符号和产生式
	for (Symbol& sym : symbols)
		cout << sym << endl;
	for (Production& prod : prods)
		cout << prod << endl;

	buildNullable();
	buildFirst();
	buildFollow();
	buildDerive();

	// 打印first, follow, derive
	for (int i = 0; i < NonTermCount; ++i){
		cout << symbols[i] << " : ";
		if (nullable[i]) cout << "null\n";
		else cout << "not null\n";
		cout << "first: ";
		for (int j = 0; j < TermCount; ++j)
			if (first[i][j]) cout << symbols[j+NonTermCount] << ", ";
		cout << "\nfollow: ";
		for (int j = 0; j < TermCount; ++j)
			if (follow[i][j]) cout << symbols[j+NonTermCount] << ", ";
		cout << "\nderive:\n";
		for (int j = 0; j < ProdCount; ++j)
			if (derive[i][j]) cout << '\t' << prods[j] << "\n";
		cout << "\n";
	}

	// 构造LR0 ItemSet graph
	ItemSetGraph isg;
	isg.build();
	cout << isg << endl;
	// 构造PDA
	buildPDA(isg);
	// 打印转移表
	displayTransfer(cout);

	cout << endl;
	ss.push(0);
}

void cp::scanNTerms(std::function<void(int)> func){
	for (int i = 0; i < NonTermCount; ++i) func(i);
}
void cp::scanTerms(std::function<void(int)> func){
	for (int i = TermStart; i < SymbolCount; ++i) func(i);
}

void displayState(std::stack<int> &ss){
	cout << "size: " << ss.size() << endl;
	int* off = &ss.top() - ss.size() + 1;
	for (size_t i = 0; i < ss.size(); ++i)
		cout << off[i] << ", ";
	cout << endl;
}

void displayToken(std::stack<Token*> &ts){
	cout << "size: " << ts.size() << endl;
	Token **off = &ts.top() - ts.size() + 1;
	for (size_t i = 0; i < ts.size(); ++i)
		cout << *off[i] << ", ";
	cout << endl;
}

int cp::doNextToken(Token* token){
	int id = token->symID;
	cout << "\n本次输入token的symbol为 " << symbols[token->symID] << endl;
	for (;;){
		int state = ss.top();
		ActionInfo &info = actionTable[state][id];
		cout << "状态栈为: ";
		displayState(ss);
		cout << "符号栈为： ";
		displayToken(ts);

		cout << "操作类型是" << typeName[info.type] << endl;
		switch(info.type){
		case Error:
			cout << "停机" << endl;
			return -1;
		case Shift:
			cout << "目的地为" << info.next << endl;
			ss.push(info.next);
			ts.push(token);
			return 0;
		default:
			Production &prod = prods[info.prodID];
			cout << "所用产生式为" << prod << endl;
			if (!prod.action()) return -1;
			if (info.type == Accept) return 1;
			for (size_t n = prod.right.size(); n; --n)
				ss.pop();
			ss.push(gotoTable[ss.top()][prod.left]);
		}
	}
	return 0;
}


















